package 中等.树;

import util.TreeNode;

import java.util.*;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-right-side-view/?plan=leetcode_75&plan_progress=s9nullg
 */
public class 二叉树的右视图_199 {

    public static void main(String[] args) {

    }

    /**
     * 广度优先搜索
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            list.add(queue.peekLast().val);

            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                if (curNode.left != null) {
                    queue.addLast(curNode.left);
                }
                if (curNode.right != null) {
                    queue.addLast(curNode.right);
                }
            }
        }

        return list;
    }


    /**
     * 深度优先搜索
     * 使用哈希表记录
     * key 代表树的深度，对应 list 的索引
     * value 代表当前深度最右边的节点值
     * <p>
     * 优先递归右节点，第一次出现当前深度的值即为最右边节点值
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();

        dfs(root, 0, map);

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            list.add(entry.getKey(), entry.getValue());
        }
        return list;
    }

    private void dfs(TreeNode node, int level, Map<Integer, Integer> map) {
        if (node == null) {
            return;
        }
        if (!map.containsKey(level)) {
            map.put(level, node.val);
        }

        dfs(node.right, level + 1, map);
        dfs(node.left, level + 1, map);
    }

}
